public class LeetCode28 {
    public static void main(String[] args) {
        String haystack = "a", needle = "a";

        System.out.println(strStr(haystack, needle));
    }

    // KMP 算法实现
    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) return 0;

        int[] pi = new int[m];

        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();

        // 构造过程 i = 1，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = pi[j - 1];
            }
            if (p[i] == p[j]) {
                j++;
            }
            pi[i] = j;
        }
        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && s[i] != s[j]) {
                j = pi[j - 1];
            }
            if (s[i] == p[j]) {
                j++;
            }
            if (m == j) {
                return i - m + 1;
            }
        }
        return -1;
    }

    public static int strStr1(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}
